class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1) {
            return true;
        }
        this.numCourses = numCourses;
        this.prerequisites = prerequisites;
        // 填充图
        fillGraph();
        // 有向图找环
        return hasCirCle();
    }
    private void fillGraph() {
        this.graph = new ArrayList<>(numCourses);
        this.inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            this.graph.add(i, new ArrayList<>());
            this.inDegree[i] = 0;
        }
        for (int[] prerequisite : this.prerequisites) {
            this.graph.get(prerequisite[1]).add(prerequisite[0]);
            this.inDegree[prerequisite[0]]++;
        }
    }
    private boolean hasCirCle() {
        List<Integer> courses = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < this.numCourses; i++) {
            if (this.inDegree[i] == 0) {
                // 没有依赖的课程先学
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            courses.add(course);
            for (int preCourse : this.graph.get(course)) {
                this.inDegree[preCourse]--;
                if (this.inDegree[preCourse] == 0) {
                    queue.offer(preCourse);
                }
            }
        }
        return courses.size() == this.numCourses;
    }
    private List<List<Integer>> graph;
    private int[] inDegree;
    private int[][] prerequisites;
    private int numCourses;
    
}

/**
[[1,4],[2,4],[3,1],[3,2]]
出边数组：
0->null
1->3
2->3
3->null
4->1->2

[0, 4, 1, 2, 3, 3]
 */
